package Hot100.Medium.LinkedList;

import java.util.Stack;

public class LC25_ReverseKGroup {
    public static void main(String[] args) {

    }

    public ListNode reverseKGroup(ListNode head, int k){
        Stack<ListNode> stack = new Stack<>();
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        while(true){ // 每K个一组循环
            int count = 0;// 重置计数器
            ListNode cur = head;// 当前组的第一个节点
            while (cur != null && count < k){
                stack.add(cur);
                cur = cur.next; // 可以看到循环结束时，cur已经是下一组的首节点了，这就是为了后面做交换
                count++;
            }
            // 如果count不等于k，证明刚才遍历时，每组数量不是k，因此直接返回。
            if(count != k){
                p.next = head;
                break;
            }
            // 开始逆序构造链表，出栈的特性就自动帮我们完成了倒叙
            while(!stack.isEmpty()){
                p.next = stack.pop();
                p = p.next;
            }
            // 移动逆序的最后一个节点指向下一组的头节点，并移动head到下一组的开始方便继续循环
            p.next = cur;
            head = cur;
        }
        return dummy.next;
    }

}
